var insertNode = function(node, newNode) {
    if (newNode.key < node.key) {
        if (node.left === null) {
            // 如果键左侧为空，则左侧成为新节点
            node.left = newNode;
        } else {
            // 如果键左侧不为空，则向下一层递归，直到找到左侧为空的键
            insertNode(node.left, newNode);
        }
    } else {
        if (node.right === null) {
            // 如果键右侧为空，则右侧成为新节点
            node.right = newNode;
        } else {
            // 如果键右侧不为空，则向下一层递归，直到找到右侧为空的键
            insertNode(node.right, newNode);
        }
    }
};

var inOrderTraverseNode = function(node, callback) {
    if (node !== null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
    }
};

var preOrderTraversNode = function(node, callback) {
    if (node !== null) {
        callback(node.key);
        preOrderTraversNode(node.left, callback);
        preOrderTraversNode(node.right, callback);
    }
};

var postOrderTraversNode = function(node, callback) {
    if (node !== null) {
        postOrderTraversNode(node.left, callback);
        postOrderTraversNode(node.right, callback);
        callback(node.key);
    }
};

var minNode = function(node) {
    if (node) {
        while (node && node.left !== null) {
            node = node.left;
        }
        return node.key;
    }
    return null;
};

var maxNode = function(node) {
    if (node) {
        while (node && node.right !== null) {
            node = node.right;
        }
        return node.key;
    }
    return null;
};

var searchNode = function(node, key) {
    if (!node) {
        return false;
    }
    if (key < node.key) {
        return searchNode(node.left, key);
    } else if (key > node.key) {
        return searchNode(node.right, key);
    } else {
        return true;
    }
};

var removeNode = function(node, key) {
    if (node === null) {
        return null;
    }
    if (key < node.key) {
        node.left = removeNode(node.left, key);
        return node;
    } else {
        if (node.left === null && node.right == null) {
            node = null;
            return node;
        }
        if (node.left === null) {
            node = node.right;
            return node;
        } else if (node.right === null) {
            node = node.left;
            return node;
        }

        var aux = findMinNode(node.right);
        node.key = aux.key;
        node.right = removeNode(node.right, aux.key);
        return node;
    }
};

var findMinNode = function(node) {
    while (node && node.left !== null) {
        node = node.left;
    }
    return node;
};

function BinarySearchTree() {
    var Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null;

    // 插入新键
    this.insert = function(key) {
        var newNode = new Node(key);
        if (root === null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    };

    // 中序遍历
    this.inOrderTraverse = function(callback) {
        inOrderTraverseNode(root, callback);
    };
    // 先序遍历
    this.preOrderTravers = function(callback) {
        preOrderTraversNode(root, callback);
    };
    // 后序遍历
    this.postOrderTravers = function(callback) {
        postOrderTraversNode(root, callback);
    };

    this.min = function() {
        return minNode(root);
    };

    this.max = function() {
        return maxNode(root);
    };

    this.search = function(key) {
        return searchNode(root, key);
    };

    this.remove = function(key) {
        root = removeNode(root, key);
    };

    this.showTree = function() {
        console.log(JSON.stringify(root, null, 2));
    };

    this.getTree = function() {
        return root;
    };
}

const binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(11);
binarySearchTree.insert(7);
binarySearchTree.insert(15);
binarySearchTree.insert(5);
binarySearchTree.insert(3);
binarySearchTree.insert(9);
binarySearchTree.insert(8);
binarySearchTree.insert(10);
binarySearchTree.insert(13);
binarySearchTree.insert(12);
binarySearchTree.insert(14);
binarySearchTree.insert(20);
binarySearchTree.insert(18);
binarySearchTree.insert(25);
binarySearchTree.insert(6);

binarySearchTree.postOrderTravers(function(value) {
    console.log(value);
});

console.log("min", binarySearchTree.min());
console.log("max", binarySearchTree.max());
console.log("search key 1", binarySearchTree.search(1) ? "found" : "not found");
console.log("search key 8", binarySearchTree.search(8) ? "found" : "not found");
